package leetcode.ms;

import java.util.PriorityQueue;
import java.util.Random;

public class MS17_14 {
    class Solution {
        public int[] smallestK(int[] arr, int k) {
            if (k <= 0) return new int[0];
            PriorityQueue<Integer> queue = new PriorityQueue<>((o1, o2) -> o2 - o1);
            for (int i = 0; i < arr.length; i++) {
                if (queue.size() < k) {
                    queue.add(arr[i]);
                } else if (queue.peek() > arr[i]) {
                    queue.poll();
                    queue.add(arr[i]);
                }
            }
            int[] res = new int[k];
            for (int i = res.length - 1; i >= 0; i--) {
                res[i] = queue.poll();
            }
            return res;
        }
    }
    class Solution2 {
        int k;
        public int[] smallestK(int[] arr, int _k) {
            k = _k;
            int n = arr.length;
            int[] ans = new int[k];
            if (k == 0) return ans;
            qsort(arr, 0, n - 1);
            for (int i = 0; i < k; i++) ans[i] = arr[i];
            return ans;
        }
        void qsort(int[] arr, int l, int r) {
            if (l >= r) return ;
            int i = l, j = r;
            int ridx = new Random().nextInt(r - l + 1) + l;
            swap(arr, ridx, l);
            int x = arr[l];
            while (i < j) {
                while (i < j && arr[j] >= x) j--;
                while (i < j && arr[i] <= x) i++;
                swap(arr, i, j);
            }
            swap(arr, i, l);
            // 集中答疑：因为题解是使用「基准点左侧」来进行描述（不包含基准点的意思），所以这里用的 k（写成 k - 1 也可以滴
            if (i > k) qsort(arr, l, i - 1);
            if (i < k) qsort(arr, i + 1, r);
        }
        void swap(int[] arr, int l, int r) {
            int tmp = arr[l];
            arr[l] = arr[r];
            arr[r] = tmp;
        }
    }
}
